//
// Created by 麻再挺 on 2021/12/20.
//

#include "bp_tree.h"

/**
 * 创建新结点
 * @return
 */
BPTree BP_Malloc_New_Node() {
    // 申请内存
    BPTree newNode = malloc(sizeof(struct BPNode));
    if (newNode == NULL) exit(EXIT_FAILURE);
    int i = 0;
    // 遍历结点数并赋值
    while (i < BP_M + 1) {
        newNode->key[i] = INT_MIN;
        newNode->children[i] = NULL;
        i++;
    }
    // 右侧兄弟结点
    newNode->next = NULL;
    newNode->keyNum = 0;
    return newNode;
}

/**
 * 初始化
 */
BPTree BP_Initialize() {
    BPTree t;
    if (BP_M < (3)) {
        printf("M最小等于3！");
        exit(EXIT_FAILURE);
    }
    // 根结点
    t = BP_Malloc_New_Node();
    return t;
}

/**
 * 当要对 x 插入 key 的时候, i 是 x 在parent 的位置, j 是 key 要插入的位置,
 * 当要对 parent 插入 x 节点的时候, i 是要插入的位置, key 和 j 的值没有作用
 * @param isKey 标识 x 插入 key 还是 parent 插入 x
 * @param parent 父节点
 * @param x 结点
 * @param key 键
 * @param i x 在 parent 的位置
 * @param j key 要插入的位置
 */
BPPosition BP_Insert_Element(int isKey, BPPosition parent, BPPosition x, BPKeyType key, int i, int j) {
    int k = 0;
    if (isKey) {
        // 插入 key
        k = x->keyNum - 1;
        // 向右移位
        while (k >= j) {
            x->key[k + 1] = x->key[k];
            k--;
        }
        // 插入数据
        x->key[j] = key;
        x->keyNum++;
    } else {
        // 插入结点
        // 对树叶结点进行连接
        if (x->children[0] == NULL) {
            if (i > 0)
                parent->children[i - 1]->next = x;
            x->next = parent->children[i];
        }
        k = parent->keyNum;
        // 移位
        while (k >= i) {
            parent->children[k + 1] = parent->children[k];
            parent->key[k] = parent->key[k - 1];
            k--;
        }
        // 只有 i 大于 0 时才操作父结点中的键
        if (i > 0) {
            parent->key[i - 1] = x->key[0];
            parent->keyNum++;
            // 如果不是叶子结点, 则进行键的删除
            if (x->children[0] != NULL) {
                x->key[i - 1] = x->key[i];
                x->key[i] = INT_MIN;
                x->keyNum--;
            }
        }
        parent->children[i] = x;
    }
    return x;
}

/**
 * 分割结点
 * @param parent 父位置
 * @param x 结点
 * @param i 所以
 * @return
 */
BPTree BP_Split_Node(BPPosition parent, BPPosition x, int i) {
    // 申请新结点
    BPPosition newNode = BP_Malloc_New_Node();
    int k = 0;
    int j = x->keyNum / 2;
    int limit = x->keyNum;
    // 移动
    while (j < limit) {
        // 移动结点, 三层及以上时走此方法快
        if (x->children[0] != NULL) {
            newNode->children[k] = x->children[j + 1];
            x->children[j + 1] = NULL;
        }
        // 赋值新结点数据
        newNode->key[k] = x->key[j];
        newNode->keyNum++;
        // 赋值原结点数据
        x->key[j] = INT_MIN;
        x->keyNum--;
        j++;
        k++;
    }
    // 插入
    if (parent != NULL) {
        BP_Insert_Element(0, parent, newNode, INT_MIN, i + 1, INT_MIN);
    } else {
        // 如果 x 是根, 那么创建新的根并返回
        parent = BP_Malloc_New_Node();
        // 插入左节点
        BP_Insert_Element(0, parent, x, INT_MIN, 0, INT_MIN);
        // 插入右结点
        BP_Insert_Element(0, parent, newNode, INT_MIN, 1, INT_MIN);
        return parent;
    }
    return x;
}

/**
 * 寻找一个兄弟结点, 其存储的关键字未满, 否则返回 NULL
 * @param parent 父节点
 * @param i 索引
 * @return 兄弟结点
 */
BPPosition BP_Find_Sibling(BPPosition parent, int i) {
    int limit = BP_M;
    BPPosition sibling = NULL;
    // 取第一个孩子结点
    if (i == 0) {
        if (parent->children[1]->keyNum < limit) {
            sibling = parent->children[1];
        }
    } else if (parent->children[i - 1]->keyNum < limit) {
        sibling = parent->children[i - 1];
    } else if (i + 1 < parent->keyNum && parent->children[i + 1]->keyNum < limit) {
        sibling = parent->children[i + 1];
    }
    return sibling;
}

/**
 * 查找最左侧的结点
 * @param p 源
 * @return
 */
BPPosition BP_Find_Most_Left(BPPosition p) {
    BPPosition tmp = p;
    while (tmp != NULL && tmp->children[0] != NULL) {
        tmp = tmp->children[0];
    }
    return tmp;
}

/**
 * 查找最右侧的结点
 * @param p 源
 * @return
 */
BPPosition BP_Find_Most_Right(BPPosition p) {
    BPPosition tmp = p;
    while (tmp != NULL && tmp->children[tmp->keyNum - 1] != NULL) {
        tmp = tmp->children[tmp->keyNum - 1];
    }
    return tmp;
}

/**
 * 移除结点
 * 当要对 x 删除 key 的时候，i 是 x 在 parent 的位置，j 是 key 要插入的位置
   当要对 parent 插入 x 节点的时候，i 是要插入的位置，key 和 j 的值没有用
 * @param isKey 标识类型
 * @param parent 父节点
 * @param x x 结点
 * @param i x 在 parent 的位置
 * @param j key 要插入的位置
 * @return
 */
BPPosition BP_Remove_Element(int isKey, BPPosition parent, BPPosition x, int i, int j) {
    int k = 0, limit = 0;
    if (isKey) {
        // 删除 key
        limit = x->keyNum;
        k = j + 1;
        // 判断是否需要向后移动
        while (k < limit) {
            x->key[k - 1] = x->key[k];
            k++;
        }
        x->key[x->keyNum - 1] = INT_MIN;
        x->keyNum--;
    } else {
        // 删除结点
        // 修改树叶结点的链接
        if (x->children[0] == NULL && i > 0) {
            parent->children[i - 1]->next = parent->children[i + 1];
        }
        limit = parent->keyNum;
        k = i;
        while (k < limit) {
            parent->children[k] = parent->children[k + 1];
            parent->key[k] = parent->key[k + 1];
            k++;
        }
        parent->children[parent->keyNum] = NULL;
        parent->key[parent->keyNum] = INT_MIN;
        parent->keyNum--;
    }
    return x;
}

/**
 * src 和 dst 是两个相邻的结点, i 是 src 在 parent 中的位置;
 * 将 src 的元素移动到 dst 中, n 是移动元素的个数
 * @param src 源结点
 * @param dst 目标结点
 * @param parent 父节点
 * @param i src 在 parent 中的位置
 * @param n 移动元素的个数
 */
BPPosition BP_Move_Element(BPPosition src, BPPosition dst, BPPosition parent, int i, int n) {
    // 孩子结点
    BPPosition child;
    BPKeyType tmpKey;
    // 标识 src 在前面
    int srcInFront = 0, j = 0;
    // 判断 src 是否在前面
    if (src->key[0] < dst->key[0]) {
        srcInFront = 1;
    }
    // 节点 src 在 dst 前面
    if (srcInFront) {
        if (src->children[0] != NULL) {
            while (j < n) {
                child = src->children[src->keyNum - 1];
                BP_Remove_Element(0, src, child, src->keyNum - 1, INT_MIN);
                BP_Insert_Element(0, dst, child, INT_MIN, 0, INT_MIN);
                j++;
            }
        } else {
            while (j < n) {
                // 取最后一个键
                tmpKey = src->key[src->keyNum - 1];
                BP_Remove_Element(1, parent, src, i, src->keyNum - 1);
                BP_Insert_Element(1, parent, dst, tmpKey, i + 1, 0);
                j++;
            }
        }
        parent->key[i] = dst->key[0];
        // 将树叶结点重新连接
        if (src->keyNum > 0)
            BP_Find_Most_Right(src)->next = BP_Find_Most_Left(dst);
    } else {
        if (src->children[0] != NULL) {
            while (j < n) {
                child = src->children[0];
                BP_Remove_Element(0, src, child, 0, INT_MIN);
                BP_Insert_Element(0, dst, child, INT_MIN, dst->keyNum, INT_MIN);
                j++;
            }
        } else {
            while (j < n) {
                tmpKey = src->key[0];
                BP_Remove_Element(1, parent, src, i, 0);
                BP_Insert_Element(1, parent, dst, tmpKey, i - 1, dst->keyNum);
                j++;
            }
        }
        parent->key[i] = src->key[0];
        if (src->keyNum > 0)
            BP_Find_Most_Right(dst)->next = BP_Find_Most_Left(src);
    }

    return parent;
}

/**
 * 按层级插入
 * @param t 树
 * @param key 键
 * @param i 索引
 * @param parent 父类
 * @return
 */
BPTree BP_Recursive_Insert(BPTree t, BPKeyType key, int i, BPTree parent) {
    // 查找分支
    int j = 0;
    while (j < t->keyNum && key >= t->key[j]) {
        // 重复值不插入
        if (key == t->key[j]) {
            return t;
        }
        j++;
    }
    // 如果存在孩子结点
    if (j != 0 && t->children[0] != NULL)j--;
    // 树叶
    if (t->children[0] == NULL)
        // 新结点插入
        t = BP_Insert_Element(1, parent, t, key, i, j);
    else
        // 内部结点
        t->children[j] = BP_Recursive_Insert(t->children[j], key, j, t);

    // 调整结点
    if (t->keyNum > BP_M - 1) {
        // 分裂结点
        t = BP_Split_Node(parent, t, i);
    }
    return t;
}

/**
 * 插入
 * @param t B+树
 * @param Key 键
 */
BPTree BP_Insert(BPTree t, BPKeyType key) {
    return BP_Recursive_Insert(t, key, 0, NULL);
}

/**
 * 查找兄弟节点，其关键字数大于M/2 ;没有返回NULL
 * @param parent 父节点
 * @param i 索引
 * @param j 位置
 * @return
 */
static BPPosition BP_Find_Sibling_KeyNum_M_2(BPPosition parent, int i, int *j) {
    int limit = BP_LIMIT_M_2;
    BPPosition sibling = NULL;
    if (i == 0) {
        if (parent->children[1]->keyNum > limit) {
            sibling = parent->children[1];
            *j = 1;
        }
    } else {
        if (parent->children[i - 1]->keyNum > limit) {
            sibling = parent->children[i - 1];
            *j = i - 1;
        } else if (i + 1 < parent->keyNum && parent->children[i + 1]->keyNum > limit) {
            sibling = parent->children[i + 1];
            *j = i + 1;
        }
    }

    return sibling;
}

/**
 * 合并节点,X少于M/2关键字，S有大于或等于M/2个关键字
 * @param parent 父节点
 * @param x x 结点
 * @param s 兄弟结点
 * @param i 索引
 * @return
 */
BPPosition BP_Merge_Node(BPPosition parent, BPPosition x, BPPosition s, int i) {
    // s 的关键字数目大于M/2
    if (s->keyNum > 1) {
        // 从 s 中移动一个元素到 x 中
        BP_Move_Element(s, x, parent, i, 1);
    } else {
        // 将 x 全部元素移动到 s 中, 并把 x 删除
        int limit = x->keyNum;
        BP_Move_Element(x, s, parent, i, limit);
        BP_Remove_Element(0, parent, x, i, INT_MIN);
        free(x);
        x = NULL;
    }
    return parent;
}

/**
 * 删除结点
 * @param t B+树结点
 * @param key 键
 * @param i 索引
 * @param parent 父结点
 * @return
 */
BPTree BP_Recursive_Remove(BPTree t, BPKeyType key, int i, BPTree parent) {
    // 查找结点
    int j = 0;
    while (j < t->keyNum && key >= t->key[j]) {
        // 判断是否相等
        if (key == t->key[j]) break;
        j++;
    }
    // 如果没有孩子结点
    if (t->children[0] == NULL) {
        // 没有找到
        if (key != t->key[j] || j == t->keyNum) return t;
    }
    // 树叶
    if (t->children[0] == NULL) {
        t = BP_Remove_Element(1, parent, t, i, j);
    } else {
        t->children[j] = BP_Recursive_Remove(t->children[j], key, j, t);
    }
    // 是否需要调整
    int needAdjust = 0;
    // 树的根或树叶, 或者其儿子树在 2 - M 之间
    if (parent == NULL && t->children[0] != NULL && t->keyNum < 1) {
        needAdjust = 1;
    } else if (parent != NULL && t->keyNum < 1) {
        // 除根外，所有非树叶节点的儿子数在[M/2]到M之间。(符号[]表示向上取整)
        // 非根）树叶中关键字的个数也在[M/2]和M之间
        needAdjust = 1;
    }
    // 调整结点
    if (needAdjust) {
        BPPosition tmp;
        // 根
        if (parent == NULL) {
            if (t->children[0] != NULL && t->keyNum < 2) {
                tmp = t;
                t = t->children[0];
                free(tmp);
                return t;
            }
        } else {
            // 查找兄弟结点
            BPPosition sibling = BP_Find_Sibling_KeyNum_M_2(parent, i, &j);
            if (sibling != NULL) {
                BP_Move_Element(sibling, t, parent, j, 1);
            } else {
                if (i == 0) {
                    sibling = parent->children[1];
                } else {
                    sibling = parent->children[i - 1];
                }
                parent = BP_Merge_Node(parent, t, sibling, i);
                t = parent->children[i];
            }
        }
    }


    return t;
}

/**
 * 删除
 * @param t B+树
 * @param Key 键
 * @return
 */
BPTree BP_Remove(BPTree t, BPKeyType key) {
    return BP_Recursive_Remove(t, key, 0, NULL);
}

/**
 * 销毁
 * @param t B+树
 */
BPTree BP_Destroy(BPTree t) {
    if (t != NULL) {
        int i = 0;
        // 销毁结点
        while (i < t->keyNum + 1) {
            BP_Destroy(t->children[i]);
            i++;
        }
        printf("Destroy: (");
        int j = 0;
        while (j < t->keyNum) {
            printf("%d:", t->key[j++]);
        }
        printf(")");
        free(t);
        t = NULL;
    }
    return t;
}

/**
 * 根据层级遍历打印
 * @param t B+树
 * @param level 层级
 */
void BP_Recursive_Travel(BPTree t, int level) {
    if (t != NULL) {
        printf(" ");
        printf("[Level:%d]-->", level);
        printf("(");
        int i = 0;
        while (i < t->keyNum) {
            printf("%d", t->key[i++]);
            if (i < t->keyNum) {
                printf(",");
            }
        }
        printf(")");
        // 层级自加
        level++;
        i = 0;
        while (i <= t->keyNum) {
            BP_Recursive_Travel(t->children[i], level);
            i++;
        }
    }
}

/**
 * 遍历节点
 * @param t B+树
 */
void BP_Travel(BPTree t) {
    BP_Recursive_Travel(t, 0);
    printf("\n");
}

/**
 * 遍历树叶节点的数据
 * @param t B+树
 */
void BP_Travel_Data(BPTree t) {
    if (t == NULL) return;
    BPPosition tmp = t;
    printf("All Data: ");
    while (tmp->children[0] != NULL) {
        tmp = tmp->children[0];
    }
    // 第一片树叶
    while (tmp != NULL) {
        int i = 0;
        while (i < tmp->keyNum) {
            printf("%d ", tmp->key[i++]);
        }
        tmp = tmp->next;
    }
    printf("\n");
}
